#include <vector>
using std::vector;

template <class K, class T>
struct Node // 结构体, 类名的命名要规范
{
    K m_key;
    T m_val;
    int m_leftsize;
    Node<K, T>* m_leftchild;
    Node<K, T>* m_rightchild;

    // 节点的创建操作
    Node<K, T>(const K& key, const T& val)
        : m_key(key)
        , m_val(val)
        , m_leftsize(0)
        , m_leftchild(nullptr)
        , m_rightchild(nullptr)
    {
    }


    // 节点的交换
    void swap(const Node<K, T>& x)
    {
        K tmp_k = m_key;
        m_key = x.m_key;
        x.m_key = tmp_k;

        T tmp_v = m_val;
        m_val = x.m_val;
        x.m_val = tmp_v;

        int tmp_s = m_leftsize;
        m_leftsize = x.m_leftsize;
        x.m_leftsize = tmp_s;

        Node<K, T>* tmp_n = m_leftchild;
        m_leftchild = x.m_leftchild;
        x.m_leftchild = tmp_n;
        tmp_n = m_rightchild;
        m_rightchild = x.m_rightchild;
        x.m_rightchild = tmp_n;
    }

};

template <class K, class T>
class IndexedBST
{
public:
    // 初始化操作, 创建一颗空树
    IndexedBST<K, T>()
        : m_root(nullptr)
        , m_size(0)
    {
    }

    // 插入操作, 插入一个新节点; 插入成功返回true, 插入失败返回false
    // 当插入的节点已存在时, 插入失败
    bool insert(const Node<K, T>& x);

    // 删除操作, By Key
    bool erase_by_key(const K& key);
    /*
        删除操作, By Index
        index从1开始
        不存在, 删除失败, 返回false

    */
    bool erase_by_index(int index);
    int eraseWithIndex(int theIndex);

    // 查找操作, By Key. 找到返回节点的地址, 找到不到返回nullptr
    Node<K, T>* find_by_key(const K& key);
    /* 
        查找操作, By Index
        index从1开始. 
        找到返回节点的地址, 找到不到返回nullptr
    */
    Node<K, T>* find_by_index(int index);

    // 一个题目的函数 key path
    bool e_sequence_key(K key, int& sum);

    // 一个题目的函数 index path
    bool e_sequence_index(int index, int& sum);

private:
    Node<K, T>* m_root;
    int m_size;
};

// 插入操作, 插入一个新节点
template <class K, class T>
bool IndexedBST<K, T>::insert(const Node<K, T>& x)
{
    // 搜索x.key是否存在, 同时寻找要放置位置的父节点
    Node<K, T>* cur = m_root;
    Node<K, T>* parent_of_cur = nullptr;

    // 只需要观察cur的流动即可
    while (cur != nullptr)
    {
        if (x.m_key == cur->m_key)
        {
            // 找到了, 不插入直接返回
            return false;
        } 
        else if (x.m_key > cur->m_key)
        {
            // 在cur的右子树
            parent_of_cur = cur;
            cur = cur->m_rightchild;
        }
        else 
        {   
            // 在cur的左子树
            parent_of_cur = cur;
            cur = cur->m_leftchild;
        }
    }

    // 最终找到了cur的父节点, 判断cur要放在哪里
    if (parent_of_cur == nullptr)
    {   
        // 说明要在插入在root位置, 这种情况不需要更新leftsize
        m_root = new Node<K, T>(x.m_key, x.m_val);
        ++m_size;
        return true;
    }
    else 
    {
        if (x.m_key > parent_of_cur->m_key)
        {
            // 放在右边
            parent_of_cur->m_rightchild = new Node<K, T>(x.m_key, x.m_val);
            ++m_size;
        }
        else if (x.m_key < parent_of_cur->m_key)
        {
            // 放在左边
            parent_of_cur->m_leftchild = new Node<K, T>(x.m_key, x.m_val);
            ++m_size;
        }
    }

    // 最后要对沿路的节点的leftsize进行更新
    cur = m_root;
    while (1)
    {
        if (x.m_key == cur->m_key)
        {
            break;
        }
        else if (x.m_key > cur->m_key )
        {
            // x在cur的右边, 不对cur的leftsize进行更新
            cur = cur->m_rightchild;
        }
        else 
        {
            // x在cur的左边, 需要对cur的leftsize进行更新
            ++cur->m_leftsize;
            cur = cur->m_leftchild;
        }
    }

    return true;
}

// 删除操作, By Key
template <class K, class T>
bool IndexedBST<K, T>::erase_by_key(const K& key)
{
    if (m_root == nullptr)
    {
        // 如果是一颗空树, 直接返回
        // 尽量只使用一个m_root成员变量
        return false;
    }

    // 找到要删除节点, 以及他的父节点
    Node<K, T>* cur = m_root;
    Node<K, T>* parent_of_cur = nullptr;
    while (cur != nullptr)
    {
        if (key == cur->m_key)
        {
            // 找到了
            break;
        }
        else if (key > cur->m_key)
        {
            // 在cur的右子树
            parent_of_cur = cur;
            cur = cur->m_rightchild;
        }
        else 
        {
            // 在cur的左子树
            parent_of_cur = cur;
            cur = cur->m_leftchild;
        }

    }

    if (cur == nullptr)
    {
        // 没找到
        return false;
    }
    else 
    {
        // 四种删除情况, 
        if (cur->m_leftchild == nullptr && cur->m_rightchild == nullptr)
        {
            // 当删除节点有0颗非空子树时, 直接删除, 改变父节点. 要么是删除右节点, 要么删除左节点
            // 先调整leftsize
            Node<K, T>* scan = m_root;
            while (1)
            {
                if (key == scan->m_key)
                {
                    break;
                }
                else if (key > scan->m_key )
                {
                    // key在scan的右边, 不对scan的leftsize进行更新
                    scan = scan->m_rightchild;
                }
                else 
                {
                    // key在scan的左边, 需要对scan的leftsize进行更新
                    --scan->m_leftsize;
                    scan = scan->m_leftchild;
                }
            }

            if (cur == m_root)
            {
                // 如果删除的是root节点时, parent_of_cur = nullptr
                m_root = nullptr;
            }
            else 
            {
                if (parent_of_cur->m_leftchild == cur)
                {
                    parent_of_cur->m_leftchild = nullptr;
                }
                else
                {
                    parent_of_cur->m_rightchild = nullptr;  
                }
            }
            
            delete cur;
            --m_size;
            
        }
        else if (cur->m_leftchild != nullptr && cur->m_rightchild == nullptr)
        {
            // 当删除节点有1颗非空子树, 且是左子树非空时, 直接用该孩子替换当前元素
            // 先调整leftsize, 
            Node<K, T>* scan = m_root;
            while (1)
            {
                if (key == scan->m_key)
                {
                    break;
                }
                else if (key > scan->m_key )
                {
                    // key在scan的右边, 不对scan的leftsize进行更新
                    scan = scan->m_rightchild;
                }
                else 
                {
                    // key在scan的左边, 需要对scan的leftsize进行更新
                    --scan->m_leftsize;
                    scan = scan->m_leftchild;
                }
            }

            if (cur == m_root)
            {
                m_root = cur->m_leftchild;
            }
            else 
            {
                if (parent_of_cur->m_leftchild == cur)
                {
                    parent_of_cur->m_leftchild = cur->m_leftchild;
                }
                else
                {
                    parent_of_cur->m_rightchild = cur->m_leftchild;  
                }
            }
            
            delete cur;
            --m_size;

        }
        else if (cur->m_leftchild == nullptr && cur->m_rightchild != nullptr)
        {
            // 当删除节点有1颗非空子树, 且是右子树非空时, 直接用该孩子替换当前元素
            // 先调整leftsize
            Node<K, T>* scan = m_root;
            while (1)
            {
                if (key == scan->m_key)
                {
                    break;
                }
                else if (key > scan->m_key )
                {
                    // key在scan的右边, 不对scan的leftsize进行更新
                    scan = scan->m_rightchild;
                }
                else 
                {
                    // key在scan的左边, 需要对scan的leftsize进行更新
                    --scan->m_leftsize;
                    scan = scan->m_leftchild;
                }
            }

            if (cur == m_root)
            {
                m_root = cur->m_rightchild;
            }
            else 
            {
                if (parent_of_cur->m_leftchild == cur)
                {
                    parent_of_cur->m_leftchild = cur->m_rightchild;
                }
                else
                {
                    parent_of_cur->m_rightchild = cur->m_rightchild;  
                }
            }

            delete cur;
            --m_size;
        }
        else  
        {
            // 当删除节点有2颗非空子树时, 替换的为右子树中最小的

            // 在右子树中一路向左, 找到右子树中最小的节点, 删除它
            Node<K, T>* substitute = cur->m_rightchild;
            Node<K, T>* parent_of_substitute = cur;
            while (substitute->m_leftchild != nullptr)
            {
                parent_of_substitute = substitute;
                substitute = substitute->m_leftchild;
            }

            // 删除substitute调整leftsize, 删除cur相当于删除substitute
            Node<K, T>* scan = m_root;
            while (1)
            {
                if (substitute->m_key == scan->m_key)
                {
                    break;
                }
                else if (substitute->m_key > scan->m_key )
                {
                    // key在scan的右边, 不对scan的leftsize进行更新
                    scan = scan->m_rightchild;
                }
                else 
                {
                    // key在scan的左边, 需要对scan的leftsize进行更新
                    --scan->m_leftsize;
                    scan = scan->m_leftchild;
                }
            }

            // cur的新的右子树
            if (parent_of_substitute != cur)
            {
                // 如果cur的右子树不止一个节点
                parent_of_substitute->m_leftchild = substitute->m_rightchild;
            }
            else 
            {
                // 如果cur的右子树只有一个节点
                cur->m_rightchild = substitute->m_rightchild;
            }

            // 再准备删除cur
            substitute->m_leftchild = cur->m_leftchild;
            substitute->m_rightchild = cur->m_rightchild;
            substitute->m_leftsize = cur->m_leftsize;
            
            if (parent_of_cur == nullptr)
            {
                // 当要删除的节点是根节点
                m_root = substitute;
            }
            else 
            {
                // 当要删除的节点不是根节点
                if (parent_of_cur->m_leftchild == cur)
                {
                    parent_of_cur->m_leftchild = substitute;
                }
                else
                {
                    parent_of_cur->m_rightchild = substitute;  
                }
            }
            

            delete cur;
            --m_size;
        }
    }

    return true;
}

/*
    删除操作, By Index
    index从1开始
*/
template <class K, class T>
bool IndexedBST<K, T>::erase_by_index(int index)
{
    Node<K, T>* object = find_by_index(index);
    if (object == nullptr)
    {
        return false;
    }
    else 
    {
        return erase_by_key(object->m_key);
    }
}

// 查找操作, By Key
template <class K, class T>
Node<K, T>* IndexedBST<K, T>::find_by_key(const K& key)
{
    Node<K, T>* cur = m_root;
    while (cur != nullptr)
    {
        if (key == cur->m_key)
        {
            // 找到了
            return cur;
        }
        else if (key > cur->m_key)
        {
            // 在cur的右子树
            cur = cur->m_rightchild;
        }
        else 
        {
            // 在cur的左子树
            cur = cur->m_leftchild;
        }
    }

    return nullptr; 
}

/* 
    查找操作, By Index
    index从1开始
*/
template <class K, class T>
Node<K, T>* IndexedBST<K, T>::find_by_index(int index)
{
    Node<K, T>* cur = m_root;
    int relative_index = index;
    while (cur != nullptr)
    {
        if (relative_index == cur->m_leftsize + 1)
        {
            return cur;
        }
        else if (relative_index > cur->m_leftsize + 1)
        {
            // 在cur的右子树, 相对index要发生改变
            relative_index = relative_index - (cur->m_leftsize + 1);
            cur = cur->m_rightchild;
        }
        else
        {
            // 在cur的左子树
            cur = cur->m_leftchild;
        }
    }

    return nullptr;
}

// 一个题目的函数 key path
template <class K, class T>
bool IndexedBST<K, T>::e_sequence_key(K key, int& sum)
{
    Node<K, T>* cur = m_root;
    
    while (cur != nullptr)
    {
        if (key == cur->m_key)
        {
            // 找到了
            sum = sum ^ cur->m_key;
            return true;
        }
        else if (key > cur->m_key)
        {
            // 在cur的右子树
            sum = sum ^ cur->m_key;
            cur = cur->m_rightchild;
        }
        else 
        {
            // 在cur的左子树
            sum = sum ^ cur->m_key;
            cur = cur->m_leftchild;
        }
    }

    // 没找到
    return false;
}

// 一个题目的函数 index path
template <class K, class T>
bool IndexedBST<K, T>::e_sequence_index(int index, int& sum)
{
    Node<K, T>* cur = m_root;
    int relative_index = index;

    while (cur != nullptr)
    {
        if (relative_index == cur->m_leftsize + 1)
        {
            sum = sum ^ cur->m_key;
            return true;
        }
        else if (relative_index > cur->m_leftsize + 1)
        {
            sum = sum ^ cur->m_key;
            relative_index = relative_index - (cur->m_leftsize + 1);
            cur = cur->m_rightchild;
        }
        else 
        {
            sum = sum ^ cur->m_key;
            cur = cur->m_leftchild;
        }
    }

    return false;
}


